package BinaryTree.快排归并;

/**
 * 链表排序 一会练！
 *
 */

import org.junit.Test;

import java.util.Arrays;

/**
 * [总结]
 *  1 递归 汉译 [闭区间]
 *  2 值传递 a=b 只可动左侧a
 *      eg. mid.next=null 不可情空右侧
 *      eg. L=res （这个虽然改了左侧 -> 参数 值 改了 -> 但 力扣 用 外部main 获取L值不变的）
 */

/**
 * 后序 1/2
 *
 * -1 5 3 4 0
 *  0 1 2 3 4
 *  0   2 3 4
 *  0 1 223344
 *  0011
 *
 *
 */
public class 归排_区间后序 {
    // 归并排序
    public int[] merge_sort(int[] nums, int l, int r){ // [闭区间]
        if(l==r){
            return new int[]{nums[l]};
        }

        // 递归 边界 暂存
        int lt = l, rt = r;

        int m = l + (r-l)/2; // m是后面递归用的 -> 不管 -> 想图 if i ti sI
        int[] L = merge_sort(nums, lt, m);
        int[] R = merge_sort(nums, m + 1, rt);

        // 后！序
        // * [大技巧] 递归 -> 汉译:  对 [闭区间] 内部排序即可
        return mergeOrderNums(L, R);
    }

    // 合并有序 数组
    /*
     1 1 2 / 1 2 3
     l       r  -> 双指针

     1 l++ [1pt 2i++ 3l++]
     while(l<n1 & r<n2)

     //反 ->
         if l==n1 for i=r <n2
         if r==n2 for i=l <n1

    */
    /*
      值传递 八股 实战：
            力扣上 本题 不能 L=res 改变参数res -> 要 fori 塞入 new int[]
            -> 因为 参数 内存地址 是个 值 不能改动 [只能改 里面的内容]
    */
    private int[] mergeOrderNums(int[] L, int[] R) {
        int[] res = new int[L.length + R.length];
        int l=0,r=0, n1=L.length, n2=R.length;

        int i=0;
        while(l<n1 && r<n2){
            if(L[l] <= R[r]){
                res[i++] = L[l++];
            }else {
                res[i++] = R[r++];
            }
        }
        if(l==n1){
            for (int j =r; j<n2 ; j++) {
                res[i++] = R[j];
            }
        }else if(r==n2){
            for (int j = l; j < n1; j++) {
                res[i++] = L[j];
            }
        }

        // 力扣上 本题 不能 L=res 改变参数res -> 要 fori 塞入 new int[]
        // -> 因为 参数 内存地址 是个 值 不能改动 [只能改 里面的内容]
//        for (int k = 0; k < L.length; k++) {
//            L[k] = res[k];
//        }
        return res;
    }

    @Test
    public void test() {
        int[] p = new int[]{-1,5,3,4,0};
        int[] res = merge_sort(p, 0, p.length - 1);

        System.out.println(Arrays.toString(res));

    }
}
